﻿//https://leetcode.cn/problems/first-missing-positive/?envType=problem-list-v2&envId=hash-table&difficulty=MEDIUM%2CHARD

class Solution {
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int n = nums.size();
        int flag = 0;
        //把所有0 负数 和大于n的数转变为1
        for (int& e : nums)
        {
            if (e == 1)
            {
                flag = 1;
            }
            else if (e < 0 || e == 0)
            {
                e = 1;
            }
        }
        //如果不存在1 说明1就是最小正整数
        if (flag == 0)
            return 1;

        //把出现正整数的值所对应的位置变为负数
        for (int i = 0; i < n; i++)
        {
            int num = abs(nums[i]);
            if (num <= n)
            {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }

        //找到第一个不为负数的位置
        for (int i = 0; i < n; i++)
        {
            if (nums[i] > 0)
            {
                return i + 1;
            }
        }

        return n + 1;

    }
};